导读：最近做了几道LeetCode的回溯问题，有点体会，在此记录防止遗忘。
要点：进入新一层递归刷新状态，递归退出时状态恢复。
描述：此题给出了一个不含重复元素的数组，要求输出该数组的所有字典序全排列。
分析：以 [1,2,3] 为例，画出决策树如下：
其中，虚线 部分表示剪枝操作，第三层递归的剪枝省略。
Java代码：
xxxxxxxxxxclass Solution { public List<List<Integer>> permute(int[] nums) { //排序非常重要，因为要按照字典序输出，将数组从小到大排列便于操作 Arrays.sort(nums); //输出List List<List<Integer>> li = new ArrayList<List<Integer>>(); //状态存储List LinkedList<Integer> tmpli = new LinkedList<Integer>(); //为了确保前一层使用的数字不能被下一层递归使用，应使用一个额外数组存放数字使用情况 int[] check = new int[nums.length]; Arrays.fill(check, 0); recursive(nums, li, tmpli, check); return li; } void recursive(int[] nums, List<List<Integer>> li, LinkedList<Integer> tmpli, int[] check){ //递归出口：如果暂存List的数字达到三个，说明是一个全排列，此时将其深复制一份放进结果List中 if(tmpli.size() == nums.length) { li.add(new ArrayList<Integer>(tmpli)); return; } else { //递归主体 for(int i=0; i<nums.length; i++){ if(check[i]==0){ //状态进入 check[i]=1; tmpli.add(nums[i]); //递归 recursive(nums, li, tmpli, check); //状态退出 tmpli.removeLast(); check[i]=0; } } } }}描述： 此题与上一题的区别在于给出的数组含有重复元素，仍要求给出字典序全排列。
分析：除了保留上一题的剪枝方法，由于重复元素的使用会导致结果集重复（例如 [1,1,2]，如果按原有剪枝策略，第二个1仍会被记录到 tmpli 中），因此要修改剪枝策略。
Java代码：
xxxxxxxxxxclass Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> li = new ArrayList<List<Integer>>(); LinkedList<Integer> tmpli = new LinkedList<Integer>(); int[] check = new int[nums.length]; Arrays.sort(nums); Arrays.fill(check, 0); backTrace(li, nums, check, tmpli); return li; } void backTrace(List<List<Integer>> li, int[] nums, int[] check, LinkedList<Integer> tmpli) { //递归出口 if(tmpli.size() == nums.length) { li.add(new ArrayList<Integer>(tmpli)); return; } //递归主体 for(int i=0; i<nums.length; i++) { //新的剪枝： //如果是同一层，且非第一次出现的，且能使用的数字，则直接跳过 //增加check[i-1]==0： //保证前一个元素在当前层仍可用 if(i>0 && nums[i]==nums[i-1] && check[i-1]==0){ continue; } if(check[i]==0){ //状态刷新 check[i] = 1; tmpli.add(nums[i]); //递归 backTrace(li, nums, check, tmpli); //状态恢复 tmpli.removeLast(); check[i] = 0; } } return; }}描述： 给出一个数组和目标值，要求给出数组中总和为目标值的所有组合，元素可以重复使用。
分析：尝试逐级递减，递归出口条件为减少至0或为负数。为了不产生重复的结果集，先对数组排序，且每次选取的元素不能超过上一次选取的值。
Java代码：
xxxxxxxxxxclass Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> li = new ArrayList<List<Integer>>(); Arrays.sort(candidates); recursive(li, candidates, target, candidates.length, new LinkedList<Integer>()); return li; } void recursive(List<List<Integer>> li, int[] candidates, int residue, int len, LinkedList<Integer> tmpli) { //递归出口 if(residue == 0){ li.add(new ArrayList<Integer>(tmpli)); return; } //引入len防止选取的值超过上一层递归的取值 for(int i=0; i<len; i++){ if(residue-candidates[i] >= 0){ //状态进入 tmpli.add(candidates[i]); //递归 recursive(li, candidates, residue-candidates[i], i+1, tmpli); //状态退出 tmpli.removeLast(); } else { return; } } }}描述：与上一题类似，但不允许使用重复的值（数组中会给出多个重复值，每个值只能用一次，如[1,1,2]）。
分析：大致与上一题类似，但每一层不允许使用重复元素，可以参考47题的剪枝，但又为了防止重复解，其剪枝方式有点不同。
Java代码：
xxxxxxxxxxclass Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> li = new ArrayList<List<Integer>>(); Arrays.sort(candidates); int[] check = new int[candidates.length]; Arrays.fill(check, 0); recursive(li, candidates, target, candidates.length, new LinkedList<Integer>(), check); return li; }void recursive(List<List<Integer>> li, int[] candidates, int residue, int len, LinkedList<Integer> tmpli, int[] check) { //递归出口 if(residue == 0){ li.add(new ArrayList<Integer>(tmpli)); return; } for(int i=0; i<len; i++){ //剪枝，不能使用上级递归已经用过的元素 if(check[i] == 1) { continue; } //剪枝，同一级不能使用重复的元素，不然导致结果集重复 if(i>0 && check[i-1]==0 && candidates[i]==candidates[i-1]){ continue; } //递归主体 if(residue-candidates[i] >= 0){ //找到相同元素中的最后一个，防止下一层递归时，有元素被漏掉 //（因为元素从小到大排列，满足条件的元素必然是有序数组中所有相同元素的第一个， // 传递截止值i会把后面相同的元素直接排除，下一级递归无法使用，导致漏解，且这样 // 做还能加快for的进行速度） while(i<len-1 && candidates[i+1] == candidates[i]){ i++; } tmpli.add(candidates[i]); check[i] = 1; recursive(li, candidates, residue-candidates[i], i, tmpli, check); check[i] = 0; tmpli.removeLast(); } else { //因为是从小到大尝试，所以出现负数说明尝试的数字太大了，不必要继续尝试 return; } } return; }}